package leecode.数组和字符串.最长回文字符串;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class MaxString {
    //方法一暴力破解
    public static void main(String[] args) {
        String string = "";
        string = "bsddbsb"; //模拟一个字符串
        int count = string.length(); //判断字符串长度
        int temp;                  //一个杯子变量
        String result = "";          //初始化结果
        boolean flog = false;       //由于可能存在不存在回文字符串,此时取值会报错，故建立一个标志决定是否进行取值
        boolean flog2 = true;
        ArrayList<Integer> Max = new ArrayList<>(); //储存与之匹配字符所在位置
        HashMap<Integer, Integer> map = new HashMap<>(); //储存初始字符与末字符的关系
//        Object obj = Collections.max(arrayList);
        for (int i = 0; i < count; i++) {   //开始遍历
            char c = string.charAt(i);
            for (int j = 0; j < count; j++) {
                if (c == string.charAt(j) && i < j) { //如果存在匹配字符则Max添加 HashMap添加关系
                    if (j >= count / 2) {
                        flog2 = false;
                    }
                    Max.add(j);
                    map.put(j, i);
                    flog = true;    //flog--->true
                }
            }
        }
        if (flog) {  //flog为true 则进行取值
            int maxnumber = Collections.max(Max);   //获取Max集合中的最大值
            temp = map.get(maxnumber);              //获取此字符串的初始位置
            result = string.substring(temp, maxnumber + 1);
        } else {
            result = "";
        }

        System.out.println(result);

    }


    //方法二，动态规划
    //new 一个布尔类似的二维数组dp[l][r] 表示(l,r)为回文字符串
    //若String.tocharAt(l)==String.tocharAt(r),则判断dp[l+1][r-1]是否为回文字符串，若是则（l,r）为回文字符串
    //第一次时dp[l][r]为true 可采用r-l<=2 如“xxxaaxxx” "xxxabaxxx"
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);

    }


}
